#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_ROWS 100
#define MAX_COLS 100

typedef struct {
    int row;
    int col;
    int distance;
} Node;

typedef struct {
    Node items[MAX_ROWS * MAX_COLS];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

bool isEmpty(Queue* q) {
    return q->front == -1;
}

void enqueue(Queue* q, Node node) {
    if (q->rear == MAX_ROWS * MAX_COLS - 1) {
        printf("Queue is full\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = node;
}

Node dequeue(Queue* q) {
    Node item = q->items[q->front];
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    }
    else {
        q->front++;
    }
    return item;
}

bool isValid(int row, int col, int rows, int cols, char grid[MAX_ROWS][MAX_COLS], bool visited[MAX_ROWS][MAX_COLS]) {
    return (row >= 0) && (row < rows) && (col >= 0) && (col < cols) && (grid[row][col] != '#') && !visited[row][col];
}

int shortestPath(char grid[MAX_ROWS][MAX_COLS], int rows, int cols, int startRow, int startCol, int endRow, int endCol) {
    bool visited[MAX_ROWS][MAX_COLS] = { false };
    Queue q;
    initQueue(&q);

    Node startNode = { startRow, startCol, 0 };
    enqueue(&q, startNode);
    visited[startRow][startCol] = true;

    int rowDirections[] = { -1, 0, 1, 0 };
    int colDirections[] = { 0, 1, 0, -1 };

    while (!isEmpty(&q)) {
        Node current = dequeue(&q);

        if (current.row == endRow && current.col == endCol) {
            return current.distance;
        }

        for (int i = 0; i < 4; i++) {
            int newRow = current.row + rowDirections[i];
            int newCol = current.col + colDirections[i];

            if (isValid(newRow, newCol, rows, cols, grid, visited)) {
                Node newNode = { newRow, newCol, current.distance + 1 };
                enqueue(&q, newNode);
                visited[newRow][newCol] = true;
            }
        }
    }

    return -1; // No path found
}

int main() {
    char grid[MAX_ROWS][MAX_COLS] = {
        {'.', '.', '.', '#', '.'},
        {'.', '#', '.', '#', '.'},
        {'.', '.', '.', '#', '.'},
        {'#', '#', '.', '.', '.'},
        {'.', '.', '.', '#', '.'}
    };

    int rows = 5;
    int cols = 5;
    int startRow = 0;
    int startCol = 0;
    int endRow = 4;
    int endCol = 4;

    int distance = shortestPath(grid, rows, cols, startRow, startCol, endRow, endCol);

    if (distance != -1) {
        printf("Shortest path distance: %d\n", distance);
    }
    else {
        printf("No path found\n");
    }

    return 0;
}